package jianzhi

func movingCount(m int, n int, k int) int {

	if k < 0 {
		return 0
	}

	vis := make([][]bool, m)
	for i := 0; i < m; i++ {
		vis[i] = make([]bool, n)
	}

	vis[0][0] = true

	res := 1

	for i := 0; i < m; i++ {
		for j := 0; j < m; j++ {
			if (i == 0 && j == 0) || helper13(i)+helper13(j) > k {
				continue
			}
			if j != 0 {
				vis[i][j] = vis[i][j-1] || vis[i][j]
			}

			if i != 0 {
				vis[i][j] = vis[i-1][j] || vis[i][j]
			}

			if vis[i][j] {
				res++
			}
		}
	}

	return res

}

func helper13(num int) int {

	res := 0

	for num > 0 {
		t := num % 10
		num = num / 10
		res += t
	}

	return res
}
